import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-11-02
 * Time: 14:19
 */


  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

public class Test {
    //汉诺塔
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }

    private void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
        if (n == 1) {
            c.add(a.remove(a.size() - 1));
            return;
        }
        dfs(a,c,b,n-1);
        c.add(a.remove(a.size() - 1));
        dfs(b,a,c,n-1);
    }

    //递归实现合并两个有序链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    //递归实现反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }

    //递归实现两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode t1 = swapPairs(head.next.next);
        ListNode t = head.next;
        t.next = head;
        head.next = t1;

        return t;
    }
}
